from __future__ import annotations


class Node:
    """
    A Node has data variable and pointers to Nodes to its left and right.
    """

    def __init__(self, data: int) -> None:
        self.data = data
        self.left: Node | None = None
        self.right: Node | None = None
 
 
def tree2list(tree: Node | None) -> list:
    '''
    tanslate tree to list
    
    >>> tree = Node(2)
    >>> tree.left=Node(3)
    >>> tree.left.left=Node(4)
    >>> tree.left.right=Node(5)
    >>> tree2list(tree)
    [2, [3, [4, [], []], [5, [], []]], []]
    '''
    if tree:
        return [tree.data,tree2list(tree.left),tree2list(tree.right)]
    else:
        return []


def tree2dict_position_data(tree, index_x=0, index_y=0, res={}) -> dict:
    '''
    tanslate tree to dict{(x,y):data}
    Notice: You must sepecify res={} when calling this function.
    
    idex_x: current layer, e.g. root --> 0
    idex_y: the index of nodes at same layer from left
    
    >>> tree = Node(2)
    >>> tree.left=Node(3)
    >>> tree.left.left=Node(4)
    >>> tree.left.right=Node(5)
    >>> tree2list_data_positions(tree,res={})
    {(0, 0): 2, (1, 0): 3, (2, 0): 4, (2, 1): 5}
    '''
    if not tree:
        return res

    res[(index_x, index_y)] = tree.data
    tree2dict_position_data(tree.left, index_x + 1, index_y * 2, res)
    tree2dict_position_data(tree.right, index_x + 1, index_y * 2 + 1, res)
                  
    # print(res)
    return res
    

def positions(depth: int) -> list:
    '''
    every node of a tree(depth) position in screen
    e.g.
           *
           7
       *       *
       3       11
     *   *   *   *
     1   5   9   13
    * * * * * * * * *
    0 2 4 6 8 ...   14
    
    >>> positions(4)
    [[7], [3, 11], [1, 5, 9, 13], [0, 2, 4, 6, 8, 10, 12, 14]]
    '''
    if depth == 0:
        return []
    
    pos = [[]]*(depth)
    pos[depth-1] = list(range(0,2**depth,2))
        
    for i in range(depth-2,-1,-1):
        pos[i] = [(pos[i+1][index]+pos[i+1][index+1])//2 for index in range(0,len(pos[i+1]),2)]
        
    return pos


def display(tree: Node | None) -> None:  # In Order traversal of the tree
    """
    >>> tree = Node(2)
    >>> tree.left=Node(3)
    >>> tree.left.left=Node(4)
    >>> tree.left.right=Node(5)
    >>> tree.left.right.right=Node(5)
    >>> display(tree)
               2        
           3            
         4   5          
              5 
    """
    depth = depth_of_tree(tree)
    pos = positions(depth)
    treeList = tree2dict_position_data(tree,res={})
    
    pos_print = {}
    while treeList:
        xy,data = treeList.popitem()
        pos_print[(xy[0],pos[xy[0]][xy[1]])] = data   
#    print(pos_print)
    
    for i in range(depth):
        for j in range(2**depth):
            try:
                print(pos_print[(i,j)],end='')
            except KeyError:
                print(' ',end='')
        print()
    

def depth_of_tree(tree: Node | None) -> int:
    """
    Recursive function that returns the depth of a binary tree.

    >>> root = Node(0)
    >>> depth_of_tree(root)
    1
    >>> root.left = Node(0)
    >>> depth_of_tree(root)
    2
    >>> root.right = Node(0)
    >>> depth_of_tree(root)
    2
    >>> root.left.right = Node(0)
    >>> depth_of_tree(root)
    3
    >>> depth_of_tree(root.left)
    2
    """
    return 1 + max(depth_of_tree(tree.left), depth_of_tree(tree.right)) if tree else 0


def is_full_binary_tree(tree: Node) -> bool:
    """
    Returns True if this is a full binary tree

    >>> root = Node(0)
    >>> is_full_binary_tree(root)
    True
    >>> root.left = Node(0)
    >>> is_full_binary_tree(root)
    False
    >>> root.right = Node(0)
    >>> is_full_binary_tree(root)
    True
    >>> root.left.left = Node(0)
    >>> is_full_binary_tree(root)
    False
    >>> root.right.right = Node(0)
    >>> is_full_binary_tree(root)
    False
    """
    if not tree:
        return True
    if tree.left and tree.right:
        return is_full_binary_tree(tree.left) and is_full_binary_tree(tree.right)
    else:
        return not tree.left and not tree.right


def main() -> None:  # Main function for testing.
    tree = Node(1)
    tree.left = Node(2)
    tree.right = Node(3)
    tree.left.left = Node(4)
    tree.left.right = Node(5)
    tree.left.right.left = Node(6)
    tree.right.left = Node(7)
    tree.right.left.left = Node(8)
    tree.right.left.left.right = Node(9)

    print(is_full_binary_tree(tree))
    print(depth_of_tree(tree))
    print("Tree is: ")
    display(tree)

    


if __name__ == "__main__":
    main()
